package com.sunny;

import java.util.*;
import java.util.concurrent.LinkedBlockingQueue;

public class Main {

    private static Stack<Node> stack = new Stack<>();
    private static Scanner scanner = new Scanner(System.in);
    private static Set<Node> used = new HashSet<>();
    private static Queue<Node> queue = new LinkedBlockingQueue<>();

    public static void main(String[] args) {

        Node root = createTreePre();

        preOrder(root);

        System.out.println("**************************");
        inOrder(root);
        System.out.println("**************************");
        postOrder(root);

        System.out.println("**************************");
        layerOrder(root);
    }

    public static Node createTreePre(){

        int val = scanner.nextInt();
        Node node = null;
        if(0 == val){
            return node;
        }
        node = new Node(val);
        node.setLeft(createTreePre());
        node.setRight(createTreePre());
        return node;

    }

    public static void preOrder(Node root){

        stack.clear();
        stack.push(root);
        while (!stack.empty()){

            Node tmp = stack.pop();
            System.out.print(tmp.getValue() + " ");
            if(null != tmp.getRight())
                stack.push(tmp.getRight());
            if(null != tmp.getLeft())
                stack.push(tmp.getLeft());
        }

    }

    public static void inOrder(Node root){

        stack.clear();
        Node current = root;
        while (null != current){
            stack.push(current);
            current = current.getLeft();
        }
        while (!stack.empty()) {
            current = stack.pop();
            System.out.print(current.getValue() + " ");
            current = current.getRight();
            while (null != current) {
                stack.push(current);
                current = current.getLeft();
            }
        }

    }

    public static void postOrder(Node root){

        used.clear();
        stack.clear();
        Node current = root;
        while (null != current){
            stack.push(current);
            current = current.getLeft();
        }
        while (!stack.empty()){
            current = stack.pop();
            if(null == current.getRight() || used.contains(current)){
                System.out.print(current.getValue() + " ");
            }else{
                stack.push(current);
                used.add(current);
                current = current.getRight();
                while (null != current) {
                    stack.push(current);
                    current = current.getLeft();
                }
            }
        }

    }

    public static void layerOrder(Node root){

        queue.clear();
        queue.add(root);
        int num = 1;
        int next = 0;

        while (!queue.isEmpty()){

            Node node = queue.poll();
            if(null == node)
                continue;
            System.out.print(node.getValue() + " ");
            if(null != node.getLeft()) {
                queue.add(node.getLeft());
                if(num > 0)
                    next++;
            }
            if(null != node.getRight()) {
                queue.add(node.getRight());
                if(num > 0)
                    next++;
            }

            num--;
            if(0 == num){
                num = next;
                next = 0;
                System.out.println();
            }
        }

    }

}

class Node{

    int value;
    Node left,right;

    public Node() {
    }

    public Node(int value) {
        this.value = value;
    }

    public Node(int value, Node left, Node right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }
}
